/**
 * 二分法
 */
public class Dichotomy {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 4, 4, 4, 5, 5, 6, 7, 9, 9, 10};
        //find(arr, 6);
        //findNum(arr, 100);
        int[] array = new int[]{4, 3, 9, 6, 2, 8, 5, 1, 6, 3, 9, 10};
        int num = getMinNum(array);
        System.out.println(num);
    }

    //无序数组，相邻不相等，求一个局部最小
    public static int getMinNum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1) {
            return 0;
        }
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int L = 0;
        int R = arr.length - 1;
        int ans = -1;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                ans = mid;
                break;
            }
            if (arr[mid] > arr[mid + 1]) {
                L = mid + 1;
                continue;
            }
            if (arr[mid] > arr[mid - 1]) {
                R = mid - 1;
                continue;
            }
        }
        return ans;
    }


    /**
     * 查找有序数组中大于等于value的最左侧位置
     */
    public static void findNum(int[] arr, int value) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空");
            return;
        }
        int L = 0;
        int R = arr.length - 1;
        int ans = -1;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (arr[mid] < value) {
                L = mid + 1;
            } else {
                ans = mid;
                R = mid - 1;
            }
        }
        if (ans == -1) {
            System.out.println("未找到" + value);
        } else {
            System.out.println("在arr[" + ans + "]找到值" + value);
        }
    }


    /**
     * 有序数组中，二分法查找数据
     *
     * @param arr
     * @param value
     * @return
     */
    public static boolean find(int[] arr, int value) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int L = 0;
        int R = arr.length - 1;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (arr[mid] == value) {
                System.out.println("在arr[" + mid + "]找到值" + value);
                return true;
            } else if (arr[mid] < value) {
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        System.out.println("未找到该值");
        return false;
    }
}
